import java.util.Arrays;
import java.util.LinkedList;

public class BinaryTrees {

    public static void main(String[] args) {
        BinaryTree<Integer> root = new BinaryTree<Integer>(239, new BinaryTree<Integer>(30), new BinaryTree<Integer>(566));
        System.out.println(root);
        System.out.println("Is it a BST? -- " + BinaryTree.isBST(root));
        final Integer[] intArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        final BinaryTree<Integer> tree = BinaryTree.buildTreeFromArray(intArray);
        /*
                            8
                       /         \
                    4              12
                  /   \         /     \
                 2     6       10     14
                / \   / \     / \     / \
               1  3  5  7    9  11   13  15
         */
        System.out.println("From array " + Arrays.toString(intArray) + " we build a tree: " + tree);
        System.out.println();
        System.out.println("Nodes lists by levels of BFS traversal:" + "");
        int levelNumber = 0;
        for (LinkedList<Integer> oneLevelNodes : BinaryTree.getListOfNodesLevelList(tree)) {
            System.out.println("[" + levelNumber + "] : " + oneLevelNodes);
            levelNumber++;
        }

        System.out.println();
        System.out.println("Is it a balanced tree?  " + tree.isBalanced());

        BinaryTree.setTheParentFields(tree, null);
        BinaryTree<Integer> treeNode = tree.search(3);
        if (treeNode != null) {
            System.out.println("Let's find next node in traversal order for " + treeNode);
            BinaryTree<Integer> nextTreeNode = treeNode.getNextNode();
            System.out.println("Here it is: " + nextTreeNode);
        }
        BinaryTree<Integer> anotherNode = tree.search(11);
        BinaryTree<Integer> parent = BinaryTree.getGCAwithParent(tree, treeNode, anotherNode);
        System.out.println();
        System.out.println("The parent for nodes " + treeNode + "  and  " + anotherNode + "  is  ");
        System.out.println(parent);
        System.out.println();
        parent = BinaryTree.getFirstCommonAncestor(tree, treeNode, anotherNode);
        System.out.println("The same task, but without using a 'parent' reference: ");
        System.out.println(parent);
        System.out.println();
        System.out.println();

        /*
                    4
                  /   \
                 2     6
                / \   / \
               1  3  5   7
         */
        BinaryTree<Integer> subTree = BinaryTree.buildTreeFromArray(Arrays.copyOf(intArray, 7));
        System.out.println("We have a subtree: " + subTree);
        System.out.println("Let's check if it's really a SUB TREE:  " + BinaryTree.isSubtree(tree, subTree));
        System.out.println();

        int sum = 10;
        System.out.println("What about sum=" + sum + "? Can we obtain it traversing the tree?");
        BinaryTree.printPathsWithGivenSum(tree, sum);

    }
}
